import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author gao
 * @date 2025/10/11 11:46
 */

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int N = in.nextInt();

            // 埃拉托斯特尼筛法生成素数列表
            boolean[] isPrime = new boolean[N + 1];
            Arrays.fill(isPrime, true);
            isPrime[0] = isPrime[1] = false;

            for (int i = 2; i * i <= N; i++) {
                if (isPrime[i]) {
                    for (int j = i * i; j <= N; j += i) {
                        isPrime[j] = false;
                    }
                }
            }

            // 收集所有素数
            List<Integer> primes = new ArrayList<>();
            for (int i = 2; i <= N; i++) {
                if (isPrime[i]) {
                    primes.add(i);
                }
            }

            int count = 0;
            int primeCount = primes.size();

            // 遍历所有可能得素数C
            for (int c = 0; c < primeCount; c++) {
                int C = primes.get(c);
                long C2 = (long) C * C;
                if (C2 > 2 * N) {
                    continue; // 如果C的平方大于2N，则不可能有满足条件的素数A和B
                }

                // 遍历所有可能的素数A
                for (int a = 0; a < primeCount; a++) {
                    int A = primes.get(a);
                    if (A >= C2) {
                        break; // A不能大于等于C2
                    }
                    long B = C2 - A;
                    if (B > N) {
                        continue; // B不能大于N
                    }
                    if (B < A) {
                        continue; // 避免重复计数
                    }
                    if (isPrime[(int) B]) {
                        if (A != B) {
                            count += 2; // (A,B,C)和(B,A,C)是两种情况
                        } else {
                            count += 1; // A和B相同的情况
                        }
                    }
                }
            }
            System.out.println(count);
        }
    }
}